#include <string>
#include <vector>
#include <unordered_set>

using namespace std;


/**
 * @brief 51. N 皇后
 * https://leetcode.cn/problems/n-queens/
 */
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<int> queens(n, -1);
        unordered_set<int> cols;
        unordered_set<int> diag1;
        unordered_set<int> diag2;

        dfs(res, n, 0, queens, cols, diag1, diag2);
        return res;
    }

    void dfs(vector<vector<string>>& res, int& n, int row, vector<int>& queens, 
        unordered_set<int>& cols, unordered_set<int>& diag1, unordered_set<int>& diag2) {
        if (row == n) {
            genResult(res, queens);
            return;
        } else {
            for (int i=0; i<n; i++) {
                if (cols.find(i) != cols.end()) continue;
                int d1 = row-i;
                if (diag1.find(d1) != diag1.end()) continue;
                int d2 = row+i;
                if (diag2.find(d2) != diag2.end()) continue;

                queens[row] = i;
                cols.insert(i);
                diag1.insert(d1);
                diag2.insert(d2);
                dfs(res, n, row+1, queens, cols, diag1, diag2);
                queens[row] = -1;
                cols.erase(i);
                diag1.erase(d1);
                diag2.erase(d2);
            }
        }
    }

    void genResult(vector<vector<string>>& res, vector<int>& queens) {
        vector<string> board;
        int n = queens.size();
        for (int i=0; i<n; i++) {
            string aRow(n, '.');
            aRow[queens[i]] = 'Q';
            board.emplace_back(aRow);
        }
        res.emplace_back(board);
    }
};
